import java.util.ArrayList;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Collections;

public class SubSumSort {
	ArrayList<Long> data;
	int [] sumArray;
	
	public void ConstructdataList(){
		PrintCurrentTime("Start ConstructdataList");
		sumArray = new int[20001];
		DataReader reader = new DataReader();
		
		if(!reader.SetFilename("C:\\tmp\\2sum.txt"))
        {
                System.out.println("failed to init file reader!");;
        }
        
		data = new ArrayList<Long>(1000000);
        String str = null;
        while((str = reader.GetNextLine()) != null)
        {
            data.add(new Long(str));    
        }
        
        Collections.sort(data);
	}
	
	public int GetHighIndexByValue(long value)
	{
		int highIndex = data.size() - 1;
		int lowIndex = 0;
		
		while(lowIndex < highIndex)
		{
			long medium = data.get((lowIndex + highIndex)/2).longValue();
			if(value == medium)
			{
				return ((lowIndex + highIndex)/2);
			}
			if(value < medium)
			{
				highIndex = (lowIndex + highIndex)/2 - 1;
			}
			else{
				lowIndex = (lowIndex + highIndex)/2 + 1;
			}
		}
		
		if(lowIndex > highIndex)
		{
			return lowIndex;
		}
		else if(data.get(lowIndex).longValue() < value)
			return (lowIndex + 1);
		else
			return lowIndex;
		
	}
	
	public int GetLowIndexByValue(long value)
	{
		int highIndex = data.size() - 1;
		int lowIndex = 0;
		
		while(lowIndex < highIndex)
		{
			long medium = data.get((lowIndex + highIndex)/2).longValue();
			if(value == medium)
			{
				return ((lowIndex + highIndex)/2);
			}
			if(value < medium)
			{
				highIndex = (lowIndex + highIndex)/2 - 1;
			}
			else{
				lowIndex = (lowIndex + highIndex)/2 + 1;
			}
		}		
		
		if(data.get(highIndex).longValue() > value)
		{
			return (highIndex - 1);
		}
		else
			return highIndex;
		
	}
	
	public void Compute2Sum(){
		PrintCurrentTime("Start Compute2Sum");
		for(int i = 0; i < data.size(); i++)
		{
			long valueX = data.get(i).longValue();
			long valueY1 = -10000 - valueX;
			long valueY2 = 10000 - valueX;
			
			int index1 = GetHighIndexByValue(valueY1);
			int index2 = GetLowIndexByValue(valueY2);
			
			for(int j = index1; j <= index2; j++)
			{
				if(valueX != data.get(j).longValue()){
					sumArray[(int)(valueX + data.get(j).longValue()) + 10000] = 1;
				}
			}
		}
		PrintCurrentTime("End Compute2Sum");
	}
	
	
	public void PrintCurrentTime(String prefix){
		System.out.println(prefix);
		SimpleDateFormat sf = new SimpleDateFormat("HH:mm:ss.SSS");
        System.out.println(sf.format(new Date()));
	}
	
	
	public void PrintData(){
		int sum = 0;
        for(int i = 0; i < sumArray.length; i++)
        {
                if(sumArray[i] != 0)
                {
                        System.out.print(i - 10000 + "\t");
                        sum++;
                }
        }
        
        System.out.print("\n");
        System.out.println("result is: " + sum);
	}

}
